package com.atguigui.leetcode1;

import java.util.Comparator;
import java.util.stream.IntStream;

/**
 * 833.字符串中的查找与替换
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/8/15 8:47
 */
public class P833FindAndReplaceInString {
    public static void main(String[] args) {
        Solution solution = new P833FindAndReplaceInString().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
            int n = s.length();
            // 空的数组，都没null
            String[] ans = new String[n];
            for (int i = 0; i < indices.length; ++i) {
                //是否需要替换 sources[i] 和 子字符相等
                if (indices[i] + sources[i].length() <= n && sources[i].equals(s.substring(indices[i], indices[i] + sources[i].length()))) {
                    // 对应的位置换成指定字符
                    ans[indices[i]] = targets[i];
                    // 超出位置变成空字符
                    for (int j = indices[i] + 1; j < indices[i] + sources[i].length(); ++j) ans[j] = "";
                }
            }
            for (int i = 0; i < n; ++i) {
                //说明该位置的字符没有被替换过，放入原始位置
                if (ans[i] == null) ans[i] = s.substring(i, i + 1);
            }
            return String.join("", ans);
        }

        public String findReplaceString2(String s, int[] indices, String[] sources, String[] targets) {
            int[] order = IntStream.range(0, indices.length).boxed().sorted(Comparator.comparingInt(i -> indices[i]))
                    .mapToInt(i -> i).toArray();
            int preIndex = 0;
            StringBuilder sb = new StringBuilder();
            for (int i : order) {
                int index = indices[i];
                sb.append(s, preIndex, index);
                if (s.startsWith(sources[i], index)) {
                    sb.append(targets[i]);
                    preIndex = index + sources[i].length();
                } else {
                    preIndex = index;
                }
            }
            sb.append(s.substring(preIndex));
            return sb.toString();
        }

    }
}
